#include <cstring>
#include <cstdio>

#define MAXN 1010
#define inf 1010000000
#define _clr(x) memset(x,0xff,sizeof(int)*n)

__int64 kuhn_munkras(int m,int n,int mat[][MAXN],int* match1,int* match2){
    int s[MAXN],t[MAXN],l1[MAXN],l2[MAXN],p,q,i,j,k;
    __int64 ret=0;
    for (i=0;i<m;i++)
        for (l1[i]=-inf,j=0;j<n;j++)
            l1[i]=mat[i][j]>l1[i]?mat[i][j]:l1[i];
    for (i=0;i<n;l2[i++]=0);
    for (_clr(match1),_clr(match2),i=0;i<m;i++){
        for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)
            for (k=s[p],j=0;j<n&&match1[i]<0;j++)
                if (l1[k]+l2[j]==mat[k][j]&&t[j]<0){
                    s[++q]=match2[j],t[j]=k;
                    if (s[q]<0)
                        for (p=j;p>=0;j=p)
                            match2[j]=k=t[j],p=match1[k],match1[k]=j;
                }
        if (match1[i]<0){
            for (i--,p=inf,k=0;k<=q;k++)
                for (j=0;j<n;j++)
                    if (t[j]<0&&l1[s[k]]+l2[j]-mat[s[k]][j]<p)
                        p=l1[s[k]]+l2[j]-mat[s[k]][j];
            for (j=0;j<n;l2[j]+=t[j]<0?0:p,j++);
            for (k=0;k<=q;l1[s[k++]]-=p);
        }
    }
    for (i=0;i<m;i++)
        ret+=mat[i][match1[i]];
    return ret;
}

int n, m, mat[ MAXN ][ MAXN ], match1[ MAXN ], match2[ MAXN ];

void init( )
{
    int i, j, u, v, w;
    scanf("%d%d", &n, &m);
    for ( i = 0; i < n; i++ )
        for ( j = 0; j < n; j++ )
            mat[ i ][ j ] = -inf;
    for ( i = 0; i < m; i++ )
    {
        scanf("%d%d%d", &u, &v, &w); u--; v--;
        if ( mat[ u ][ v ] < -w )
            mat[ u ][ v ] = -w;
        if ( mat[ v ][ u ] < -w )
            mat[ v ][ u ] = -w;
    }
}

int main( )
{
    int t, cas = 1;
    __int64 p;
    scanf("%d", &t);
    while ( t-- )
    {
        init( );
        p = -kuhn_munkras( n, n, mat, match1, match2 );
        printf("Case %d: ", cas++);
        if ( p < inf )
            printf("%I64d\n", p);
        else
            puts("NO");
    }
    return 0;
}
